package 蓝桥杯算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class day17 {
    public static void main(String[] args) {
      /*  int[] arr={1,1,2};
        day17 a=new day17();
       System.out.println(a.permute2(arr).toString());
        String[][] num={{"MUC", "LHR"}, {"JFK", "MUC"},{"SFO", "SJC"},{"LHR", "SFO"}};
        System.out.println(a.permute5(num).toString());
       List<List<String>> s=a.solven(5);
        System.out.println(s);*/
        int[] arr1={1,2,3,4};
        int[] arr2={1,3,4};
        day17 a=new day17();
        System.out.println(a.findbest(arr1,arr2));
    }
    List<List<Integer>> result=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public List<List<Integer>> sunsort(int[] arr){
        Arrays.sort(arr);
        backing(arr,0);
        return result;
    }
    public void backing(int[] arr,int start){
        result.add(new ArrayList<>(path));
        if(start==arr.length){
            return;
        }
        for(int i=start;i<arr.length;i++){
            if(i>start&&arr[i]==arr[i-1]){//写在循环里面，确保小层次不重复
                continue;
            }
            path.add(arr[i]);
            backing(arr,i+1);
            path.removeLast();
        }
    }





    List<List<Integer>> result1=new ArrayList<>();
    LinkedList<Integer> path1=new LinkedList<>();
    public List<List<Integer>> findSunsort(int[] arr, int[] arr2){
        Arrays.sort(arr);
        backTracing(arr,0);
        return result1;
    }
    public void backTracing(int[] arr,int start){
        if(path1.size()>=2){//结果的添加最好放在最前面
            result1.add(new ArrayList<>(path1));
        }
        if(start==arr.length){
            return;
        }
        for(int i=start;i<arr.length;i++){
            if(i>start&&arr[i]==arr[i-1]){
                continue;
            }
            path1.add(arr[i]);
            backTracing(arr,i+1);
            path1.removeLast();



        }

    }
    List<List<Integer>> result3=new ArrayList<>();
    LinkedList<Integer> path3=new LinkedList<>();
    public List<List<Integer>> permute(int[] num){
        if(num.length==0){
            return null;
        }
        boolean[] used=new boolean[num.length];
        backTracing1(num,used);
        return result3;
    }
    private void backTracing1(int[] num,boolean[] used){

        if(path3.size()==num.length){
            result3.add(new ArrayList<>(path3));
            return;
        }
        for(int i=0;i<num.length;i++){
            if(used[i]){
                continue;
            }
            used[i]=true;
            path3.add(num[i]);
            backTracing1(num,used);//聪明！！
            path3.removeLast();
            used[i]=false;//每一层都有，used数组防止重复
        }
    }
    List<List<Integer>> result4=new ArrayList<>();
    LinkedList<Integer> path4=new LinkedList<>();
    public List<List<Integer>> permute2(int[] nums){
        boolean[] used=new boolean[nums.length];
        Arrays.fill(used,false);
        Arrays.sort(nums);
        if(nums.length==0){
            return null;
        }

        backTracking3(nums,used);
        return result4;
    }
    private void backTracking3(int[] nums,boolean[] used){
        if(path4.size()==nums.length){
            result4.add(new ArrayList<>(path4));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false){//规避第二个，重复的可能
                continue;
            }
         if(used[i]){
             continue;
         }
            used[i]=true;
            path4.add(nums[i]);
            backTracking3(nums,used);
            path4.removeLast();
            used[i]=false;
        }
    }
    List<List<String>> result5=new ArrayList<>();
    LinkedList<String> path5=new LinkedList<>();
    public List<List<String>> permute5(String[][]nums){
        if(nums.length==0){
            return null;
        }
        backTracking4(nums);
        return result5;
    }
    public void backTracking4(String[][] nums){
        if(path5.size()==nums.length){
            result5.add(new ArrayList<>(path5));
        }
        String record=null;
       for(int i=0;i<nums.length;i++){
           if(path5.size()==nums.length){
               result5.add(new ArrayList<>(path5));
               return;
           }
           if(nums[i][0]=="JFK"){
               path5.add(nums[i][0]);
               path5.add(nums[i][1]);
               record=nums[i][1];
               break;
           }
       }

       for(int i=0;i<nums.length;i++) {
           if (nums[i][0] == record) ;
           path5.add(nums[i][1]);
           record = nums[i][1];
       }
    }

    List<List<String>> result6=new ArrayList<>();
    public List<List<String>> solven(int n){
        char[][]chese=new char[n][n];
        for (char[] c : chese) {
            Arrays.fill(c, '.');
        }
        backTrack(n,0,chese);
        return result6;
    }
    private void backTrack(int n,int row,char[][]chars){
        if(row==n){
            result6.add(Array2List(chars));
            return;
        }
        for(int i=0;i<row;++i){
            //行由回输支配，列由循环支配
            if(isvalid(row,i,n,chars)){
                chars[row][i]='Q';
                backTrack(n,row+1,chars);
                chars[row][i]='.';
            }
        }
    }
    public List Array2List(char[][] arr){
        List<String> list=new ArrayList<>();
        for(char[] c:arr){
            list.add(String.copyValueOf(c));
        }
        return list;
    }
    private boolean isvalid(int row,int col,int n,char[][] arr){
        for(int i=0;i<row;++i) {
            if (arr[row][i] == 'Q') {
                return false;
            }
        }
            for(int a=row-1,b=col-1;a>=0&&b>=0;a--,b--){//不用遍历后面的，后面都是空的
                if(arr[a][b]=='Q'){
                    return false;
                }
            }
            for(int x=row-1,y=col+1;x>=0&&y<=n-1;x--,y++){
                if(arr[x][y]=='Q'){
                    return false;
                }
            }
        return true;
    }
    public int findbest(int[] g,int[] s){
        Arrays.sort(g);
        Arrays.sort(s);
        int start=0;
        int count=0;
        for(int i=0;i<g.length&&start<s.length;i++){
            if(g[start]<=s[i]){
                start++;
                count++;
            }
        }
        return count;
    }


}
